#include <iostream>

using namespace std;

const size_t COUNT = 5;

struct Node{
	int data;
	Node *next;
	Node *randomNext;

	Node(int _data = 0) : data(_data){}
};

// Create a single link list
Node* createLinkList(size_t count){
	if(count <= 0)
		return NULL;
	Node *root = new Node();
	root->data = 1;
	root->next = NULL;
	root->randomNext = NULL;

	Node *cur = root;
	for(size_t i = 0; i < count -1; i ++){		
		cur->next = new Node();
		cur = cur->next;
		cur->data = i + 2;
		cur->next = NULL;
		cur->randomNext = NULL;
	}

	return root;
}

// Add random link
void createRandomLink(Node *root, size_t count){
	Node *cur = root, *randomNext = root;
	size_t dist = 0, index = 0;
	while(cur != NULL){
		randomNext = root;
		dist = rand() % count;
		while(index ++ < dist){
			randomNext = randomNext->next;
		}
		cur->randomNext = randomNext;
		cur = cur->next;
	}
}

// print the list
void printList(Node *list){
	Node *cur = list;
	Node *temp = list;
	int cu = -1, next = 0, randomNext = 0;
	while(cur != NULL){
		cu ++;
		next = 0;
		randomNext = 0;
		
		temp = list;
		while(temp != cur->next){
			next ++;
			temp = temp->next;
		}
		temp = list;
		while(temp != cur->randomNext){
			randomNext ++;
			temp = temp->next;
		}
		cout << "Current Node: " << cu << ", Next Node: " << next << ", Random Next Node: " << randomNext << endl;
		cout << "Current Node: " << cur->data << ", Next Node: " << (cur->next == NULL ? 0 : cur->next->data) << ", Random Next Node: " << cur->randomNext->data << endl;
		cur = cur->next;
	}
	cout << endl << endl;
}

// Copy the link list with random link
Node *copyLinkList(Node *linkList){ // const Node * cannot initialize Node *
	if(NULL == linkList)
		return NULL;

	Node *newListRoot = new Node();
	Node *oldCur = linkList, *newCur = newListRoot;
	
	while(oldCur->next != NULL){
		newCur->next = new Node();
		newCur = newCur->next;
		newCur->randomNext = NULL;
		oldCur =oldCur->next;
	}

	Node *oldTemp = NULL, *newTemp = NULL;
	newCur = newListRoot;
	oldCur = linkList;
	while(oldCur != NULL){
		oldTemp = linkList;
		newTemp = newListRoot;
		while(oldTemp != oldCur->randomNext){
			newTemp = newTemp ->next;
			oldTemp = oldTemp->next;
		}
		newCur->randomNext = newTemp;

		oldCur = oldCur->next;
		newCur = newCur->next;
	}

	return newListRoot;
}

// Optimized
Node *copyLinkListOptimazed(Node *linkList){
	if(NULL == linkList)
		return NULL;

	Node *newList = new Node();
	Node *tempList = new Node();

	Node *newCur = newList;
	Node *srcCur = linkList;
	Node *tempCur = tempList;
	
	while(srcCur->next != NULL){
		newCur->next = new Node();
		newCur->randomNext =srcCur;

		tempCur->next = new Node();
		tempCur->randomNext = srcCur;

		srcCur = srcCur->next;
		newCur->randomNext->next = newCur;

		newCur = newCur->next;
		tempCur = tempCur->next;
	}

	// the last node
	newCur->next = NULL;
	newCur->randomNext = srcCur;

	tempCur->next = NULL;
	tempCur->randomNext = srcCur;

	srcCur->next = newCur;

	// copye randomNext
	newCur = newList;
	while(newCur->next != NULL){
		newCur->randomNext = newCur->randomNext->randomNext->next;
		newCur = newCur->next;
	}
	newCur->randomNext = newCur->randomNext->randomNext->next;
		
	// recover the next link of srclist
	tempCur = tempList->next;
	srcCur = linkList;
	while(tempCur->next != NULL){
		srcCur->next = tempCur->randomNext;
		srcCur = srcCur->next;
		tempCur = tempCur->next;
	}
	srcCur->next = tempCur->randomNext;
	srcCur->next->next = NULL;

	return newList;
}
// Without hader
Node *copyLinkListWithoutHeader(Node *linkList){
	if(NULL == linkList)
		return NULL;

	Node *newList = new Node(linkList->data + 10);
	Node *tempList = new Node(linkList->data + 100);

	Node *newCur = newList;
	Node *tempCur = tempList;
	Node *srcCur = linkList->next;

	newCur->randomNext = linkList;
	tempCur->randomNext = linkList;
	linkList->next = newCur;
	
	while(srcCur != NULL){
		newCur->next = new Node(srcCur->data + 10);
		newCur = newCur->next;
		newCur->next = NULL;
		newCur->randomNext =srcCur;

		tempCur->next = new Node(srcCur->data + 100);
		tempCur = tempCur->next;
		tempCur->next = NULL;
		tempCur->randomNext = srcCur;

		srcCur = srcCur->next;
		newCur->randomNext->next = newCur;
	}

	// copye randomNext
	newCur = newList;
	while(newCur != NULL){
		newCur->randomNext = newCur->randomNext->randomNext->next;
		newCur = newCur->next;
	}
		
	// recover the next link of srclist
	tempCur = tempList->next;
	srcCur = linkList;
	while(tempCur != NULL){
		srcCur->next = tempCur->randomNext;
		srcCur = srcCur->next;
		tempCur = tempCur->next;
	}
	srcCur->next = NULL;

	return newList;
}

// With hader
Node *copyLinkListWithHeader(Node *linkList){
	if(NULL == linkList)
		return NULL;

	Node *newListHeader = new Node();
	newListHeader->next = NULL;
	newListHeader->randomNext = NULL;

	Node *tempListHeader = new Node();
	tempListHeader->next = NULL;
	tempListHeader->randomNext = NULL;

	Node *newCur = newListHeader;
	Node *tempCur = tempListHeader;
	Node *srcCur = linkList->next;

	while(srcCur != NULL){
		newCur->next = new Node(srcCur->data + 10);
		newCur = newCur->next;
		newCur->next = NULL;
		newCur->randomNext =srcCur;

		tempCur->next = new Node(srcCur->data + 100);
		tempCur = tempCur->next;
		tempCur->next = NULL;
		tempCur->randomNext = srcCur;

		srcCur = srcCur->next;
	}

	// copye randomNext
	newCur = newListHeader->next;
	while(newCur != NULL){
		newCur->randomNext = newCur->randomNext->randomNext->next;
		newCur = newCur->next;
	}
		
	// recover the next link of srclist
	tempCur = tempListHeader->next->next;
	srcCur = linkList->next;
	while(tempCur != NULL){
		srcCur->next = tempCur->randomNext;
		srcCur = srcCur->next;
		tempCur = tempCur->next;
	}
	srcCur->next = NULL;

	return newListHeader;
}

int slwrlcmain(int argc, char **argv){
	Node *linkList = createLinkList(COUNT);
	createRandomLink(linkList, COUNT);
	Node *header = new Node();
	header->next = linkList;

	Node *newList = copyLinkListOptimazed(linkList);
	Node *newList2 = copyLinkListWithoutHeader(linkList);
	Node *newList3 = copyLinkListWithHeader(header);

	printList(linkList);
	printList(newList);
	printList(newList2);
	printList(newList3->next);

	return 0;
}